//
// GPSMapEdit
// (c) Konstantin Galichsky (kg@geopainting.com), 2005
//
// Fast square root.
//

# include "StdAfx.h"
# include "fast_sqrt.h"

# define SqrtBit(k) \
	t = s + (1UL << (k - 1)); t <<= k + 1; if (_n >= t) {_n -= t; s |= 1UL << k;}

unsigned long isqrt (unsigned long _n) {
	DWORD s = 0UL;
	if (_n >= (1UL << 30)) {
		_n -= (1UL << 30);
		s = (1UL << 15);
	}
	DWORD t;
	SqrtBit (14);
	SqrtBit (13);
	SqrtBit (12);
	SqrtBit (11);
	SqrtBit (10);
	SqrtBit (9);
	SqrtBit (8);
	SqrtBit (7);
	SqrtBit (6);
	SqrtBit (5);
	SqrtBit (4);
	SqrtBit (3);
	SqrtBit (2);
	SqrtBit (1);
	if (_n > (s << 1))
		s |= 1UL;

	return s;
}
